/*-------------------------------------------------------------------------
 *
 * rangetypes_gist.c
 *	  GiST 对范围类型的支持。
 *
 * Portions Copyright (c) 1996-2022, PostgreSQL Global Development Group
 * Portions Copyright (c) 1994, Regents of the University of California
 *
 *
 * IDENTIFICATION
 *	  src/backend/utils/adt/rangetypes_gist.c
 *
 *-------------------------------------------------------------------------
 */
#include "postgres.h"

#include "access/gist.h"
#include "access/stratnum.h"
#include "utils/datum.h"
#include "utils/float.h"
#include "utils/fmgrprotos.h"
#include "utils/multirangetypes.h"
#include "utils/rangetypes.h"

/*
 * 在 GiST 中用于区分不同范围类的范围类属性。
 * 每个唯一的属性组合就是一个类。 CLS_EMPTY 不能与其他任何属性组合。
 */
#define CLS_NORMAL			0	/* 普通有限范围（没有设置位） */
#define CLS_LOWER_INF		1	/* 下边界是无穷大 */
#define CLS_UPPER_INF		2	/* 上边界是无穷大 */
#define CLS_CONTAIN_EMPTY	4	/* 包含底层空范围 */
#define CLS_EMPTY			8	/* 空范围的特殊类 */

#define CLS_COUNT			9	/* 类别数量；包括所有属性的组合。 CLS_EMPTY 不与其他任何属性组合，所以它只能是 2^3 + 1。 */

/*
 * 接受的同类项目的最小拆分比例。如果项目属于不同类别，我们将按照这些类别进行拆分，无论比例如何。
 */
#define LIMIT_RATIO  0.3

/* 固定惩罚值的常量 */
#define INFINITE_BOUND_PENALTY	2.0
#define CONTAIN_EMPTY_PENALTY  1.0
#define DEFAULT_SUBTYPE_DIFF_PENALTY  1.0

/*
 * range_gist_single_sorting_split 的每个项目数据。
 */
typedef struct
{
	int			index;
	RangeBound	bound;
} SingleBoundSortItem;

/* 在拆分的左侧或右侧放置？ */
typedef enum
{
	SPLIT_LEFT = 0,				/* 使初始化到 SPLIT_LEFT 更加容易 */
	SPLIT_RIGHT
} SplitLR;

/*
 * range_gist_consider_split 的上下文。
 */
typedef struct
{
	TypeCacheEntry *typcache;	/* 范围类型的 typcache */
	bool		has_subtype_diff;	/* 是否具有 subtype_diff？ */
	int			entries_count;	/* 被拆分的条目总数 */

	/* 目前选定拆分的信息如下 */

	bool		first;			/* 如果尚未选择拆分则为真 */

	RangeBound *left_upper;		/* 左间隔的上限 */
	RangeBound *right_lower;	/* 右间隔的下限 */

	float4		ratio;			/* 拆分比例 */
	float4		overlap;		/* 左侧和右侧谓词之间的重叠 */
	int			common_left;	/* destined for each side 的共同条目数量 */
	int			common_right;
} ConsiderSplitContext;

/*
 * 从非空范围提取的边界，用于
 * range_gist_double_sorting_split。
 */
typedef struct
{
	RangeBound	lower;
	RangeBound	upper;
} NonEmptyRange;

/*
 * 表示可以放置在任一组中的条目信息
 * 而不影响选定轴上的重叠（“公共条目”）。
 */
typedef struct
{
	/* 初始数组中条目的索引 */
	int			index;
	/* 范围与两个组的接近程度之间的差值 */
	double		delta;
} CommonEntry;

/* 在拆分过程中将条目放置在左组或右组的辅助宏 */
/* 注意直接访问变量 v, typcache, left_range, right_range */
#define PLACE_LEFT(range, off)					\
	do {										\
		if (fc_v->spl_nleft > 0)					\
			fc_left_range = fc_range_super_union(fc_typcache, fc_left_range, range); \
		else									\
			fc_left_range = (range);				\
		fc_v->spl_left[fc_v->spl_nleft++] = (off);	\
	} while(0)

#define PLACE_RIGHT(range, off)					\
	do {										\
		if (fc_v->spl_nright > 0)					\
			fc_right_range = fc_range_super_union(fc_typcache, fc_right_range, range); \
		else									\
			fc_right_range = (range);				\
		fc_v->spl_right[fc_v->spl_nright++] = (off);	\
	} while(0)

/* 复制一个 RangeType 数据（为范围硬编码 typbyval 和 typlen...） */
#define rangeCopy(r) \
	((RangeType *) DatumGetPointer(datumCopy(PointerGetDatum(r), \
											 false, -1)))

static RangeType *fc_range_super_union(TypeCacheEntry *fc_typcache, RangeType *fc_r1,
									RangeType *fc_r2);
static bool fc_range_gist_consistent_int_range(TypeCacheEntry *fc_typcache,
											StrategyNumber fc_strategy,
											const RangeType *fc_key,
											const RangeType *fc_query);
static bool fc_range_gist_consistent_int_multirange(TypeCacheEntry *fc_typcache,
												 StrategyNumber fc_strategy,
												 const RangeType *fc_key,
												 const MultirangeType *fc_query);
static bool fc_range_gist_consistent_int_element(TypeCacheEntry *fc_typcache,
											  StrategyNumber fc_strategy,
											  const RangeType *fc_key,
											  Datum fc_query);
static bool fc_range_gist_consistent_leaf_range(TypeCacheEntry *fc_typcache,
											 StrategyNumber fc_strategy,
											 const RangeType *fc_key,
											 const RangeType *fc_query);
static bool fc_range_gist_consistent_leaf_multirange(TypeCacheEntry *fc_typcache,
												  StrategyNumber fc_strategy,
												  const RangeType *fc_key,
												  const MultirangeType *fc_query);
static bool fc_range_gist_consistent_leaf_element(TypeCacheEntry *fc_typcache,
											   StrategyNumber fc_strategy,
											   const RangeType *fc_key,
											   Datum fc_query);
static void fc_range_gist_fallback_split(TypeCacheEntry *fc_typcache,
									  GistEntryVector *fc_entryvec,
									  GIST_SPLITVEC *fc_v);
static void fc_range_gist_class_split(TypeCacheEntry *fc_typcache,
								   GistEntryVector *fc_entryvec,
								   GIST_SPLITVEC *fc_v,
								   SplitLR *fc_classes_groups);
static void fc_range_gist_single_sorting_split(TypeCacheEntry *fc_typcache,
											GistEntryVector *fc_entryvec,
											GIST_SPLITVEC *fc_v,
											bool fc_use_upper_bound);
static void fc_range_gist_double_sorting_split(TypeCacheEntry *fc_typcache,
											GistEntryVector *fc_entryvec,
											GIST_SPLITVEC *fc_v);
static void fc_range_gist_consider_split(ConsiderSplitContext *fc_context,
									  RangeBound *fc_right_lower, int fc_min_left_count,
									  RangeBound *fc_left_upper, int fc_max_left_count);
static int	get_gist_range_class(RangeType *fc_range);
static int	fc_single_bound_cmp(const void *fc_a, const void *fc_b, void *fc_arg);
static int	fc_interval_cmp_lower(const void *fc_a, const void *fc_b, void *fc_arg);
static int	fc_interval_cmp_upper(const void *fc_a, const void *fc_b, void *fc_arg);
static int	fc_common_entry_cmp(const void *fc_i1, const void *fc_i2);
static float8 fc_call_subtype_diff(TypeCacheEntry *fc_typcache,
								Datum fc_val1, Datum fc_val2);


/* GiST 查询一致性检查 */
Datum range_gist_consistent(PG_FUNCTION_ARGS)
{
	GISTENTRY  *fc_entry = (GISTENTRY *) PG_GETARG_POINTER(0);
	Datum		fc_query = PG_GETARG_DATUM(1);
	StrategyNumber fc_strategy = (StrategyNumber) PG_GETARG_UINT16(2);
	bool		fc_result;
	Oid			fc_subtype = PG_GETARG_OID(3);
	bool	   *fc_recheck = (bool *) PG_GETARG_POINTER(4);
	RangeType  *fc_key = DatumGetRangeTypeP(fc_entry->key);
	TypeCacheEntry *fc_typcache;

	/* 此函数服务的所有运算符都是精确的 */
	*fc_recheck = false;

	fc_typcache = range_get_typcache(fcinfo, RangeTypeGetOid(fc_key));

	/*
	 * 使用与关键类型（叶子或内部）和查询子类型（范围、多范围或元素）
	 * 相对应的函数进行一致性检查。
	 * 请注意，非法子类型意味着查询类型与关键类型匹配
	 * （范围）。
	 */
	if (GIST_LEAF(fc_entry))
	{
		if (!OidIsValid(fc_subtype) || fc_subtype == ANYRANGEOID)
			fc_result = fc_range_gist_consistent_leaf_range(fc_typcache, fc_strategy, fc_key,
													  DatumGetRangeTypeP(fc_query));
		else if (fc_subtype == ANYMULTIRANGEOID)
			fc_result = fc_range_gist_consistent_leaf_multirange(fc_typcache, fc_strategy, fc_key,
														   DatumGetMultirangeTypeP(fc_query));
		else
			fc_result = fc_range_gist_consistent_leaf_element(fc_typcache, fc_strategy,
														fc_key, fc_query);
	}
	else
	{
		if (!OidIsValid(fc_subtype) || fc_subtype == ANYRANGEOID)
			fc_result = fc_range_gist_consistent_int_range(fc_typcache, fc_strategy, fc_key,
													 DatumGetRangeTypeP(fc_query));
		else if (fc_subtype == ANYMULTIRANGEOID)
			fc_result = fc_range_gist_consistent_int_multirange(fc_typcache, fc_strategy, fc_key,
														  DatumGetMultirangeTypeP(fc_query));
		else
			fc_result = fc_range_gist_consistent_int_element(fc_typcache, fc_strategy,
													   fc_key, fc_query);
	}
	PG_RETURN_BOOL(fc_result);
}

/*
 * 用于多范围的 GiST 压缩方法：多范围被近似为没有间隙的并集
 * 范围。
 */
Datum multirange_gist_compress(PG_FUNCTION_ARGS)
{
	GISTENTRY  *fc_entry = (GISTENTRY *) PG_GETARG_POINTER(0);

	if (fc_entry->leafkey)
	{
		MultirangeType *fc_mr = DatumGetMultirangeTypeP(fc_entry->key);
		RangeType  *fc_r;
		TypeCacheEntry *fc_typcache;
		GISTENTRY  *fc_retval = palloc(sizeof(GISTENTRY));

		fc_typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(fc_mr));
		fc_r = multirange_get_union_range(fc_typcache->rngtype, fc_mr);

		gistentryinit(*fc_retval, RangeTypePGetDatum(fc_r),
					  fc_entry->rel, fc_entry->page, fc_entry->offset, false);

		PG_RETURN_POINTER(fc_retval);
	}

	PG_RETURN_POINTER(fc_entry);
}

/* 多范围的 GiST 查询一致性检查 */
Datum multirange_gist_consistent(PG_FUNCTION_ARGS)
{
	GISTENTRY  *fc_entry = (GISTENTRY *) PG_GETARG_POINTER(0);
	Datum		fc_query = PG_GETARG_DATUM(1);
	StrategyNumber fc_strategy = (StrategyNumber) PG_GETARG_UINT16(2);
	bool		fc_result;
	Oid			fc_subtype = PG_GETARG_OID(3);
	bool	   *fc_recheck = (bool *) PG_GETARG_POINTER(4);
	RangeType  *fc_key = DatumGetRangeTypeP(fc_entry->key);
	TypeCacheEntry *fc_typcache;

	/*
	 * 此函数服务的所有运算符都是不精确的，因为多范围
	 * 被近似为没有间隙的并集范围。
	 */
	*fc_recheck = true;

	fc_typcache = range_get_typcache(fcinfo, RangeTypeGetOid(fc_key));

	/*
	 * 使用与关键类型（叶子或内部）和查询子类型（范围、多范围或元素）
	 * 相对应的函数进行一致性检查。
	 * 请注意，非法子类型意味着查询类型与关键类型匹配
	 * （多范围）。
	 */
	if (GIST_LEAF(fc_entry))
	{
		if (!OidIsValid(fc_subtype) || fc_subtype == ANYMULTIRANGEOID)
			fc_result = fc_range_gist_consistent_leaf_multirange(fc_typcache, fc_strategy, fc_key,
														   DatumGetMultirangeTypeP(fc_query));
		else if (fc_subtype == ANYRANGEOID)
			fc_result = fc_range_gist_consistent_leaf_range(fc_typcache, fc_strategy, fc_key,
													  DatumGetRangeTypeP(fc_query));
		else
			fc_result = fc_range_gist_consistent_leaf_element(fc_typcache, fc_strategy,
														fc_key, fc_query);
	}
	else
	{
		if (!OidIsValid(fc_subtype) || fc_subtype == ANYMULTIRANGEOID)
			fc_result = fc_range_gist_consistent_int_multirange(fc_typcache, fc_strategy, fc_key,
														  DatumGetMultirangeTypeP(fc_query));
		else if (fc_subtype == ANYRANGEOID)
			fc_result = fc_range_gist_consistent_int_range(fc_typcache, fc_strategy, fc_key,
													 DatumGetRangeTypeP(fc_query));
		else
			fc_result = fc_range_gist_consistent_int_element(fc_typcache, fc_strategy,
													   fc_key, fc_query);
	}
	PG_RETURN_BOOL(fc_result);
}

/* 形成并集范围 */
Datum range_gist_union(PG_FUNCTION_ARGS)
{
	GistEntryVector *fc_entryvec = (GistEntryVector *) PG_GETARG_POINTER(0);
	GISTENTRY  *fc_ent = fc_entryvec->vector;
	RangeType  *fc_result_range;
	TypeCacheEntry *fc_typcache;
	int			fc_i;

	fc_result_range = DatumGetRangeTypeP(fc_ent[0].key);

	fc_typcache = range_get_typcache(fcinfo, RangeTypeGetOid(fc_result_range));

	for (fc_i = 1; fc_i < fc_entryvec->n; fc_i++)
	{
		fc_result_range = fc_range_super_union(fc_typcache, fc_result_range,
										 DatumGetRangeTypeP(fc_ent[fc_i].key));
	}

	PG_RETURN_RANGE_P(fc_result_range);
}

/*
 * 我们将范围作为范围存储在 GiST 索引中，因此我们不需要
 * 压缩、解压或提取函数。请注意，这意味着对可以索引的范围值
 * 的大小有限制。
 */

/*
 * GiST 页面拆分惩罚函数。
 *
 * 惩罚函数的目标如下（按重要性排序）：
 * - 保持正常范围分开
 * - 避免扩大原始谓词的类别
 * - 避免根据 subtype_diff 扩大原始谓词
 * - 优先将范围添加到较窄的原始谓词
 */
Datum range_gist_penalty(PG_FUNCTION_ARGS)
{
	GISTENTRY  *fc_origentry = (GISTENTRY *) PG_GETARG_POINTER(0);
	GISTENTRY  *fc_newentry = (GISTENTRY *) PG_GETARG_POINTER(1);
	float	   *fc_penalty = (float *) PG_GETARG_POINTER(2);
	RangeType  *fc_orig = DatumGetRangeTypeP(fc_origentry->key);
	RangeType  *fc_new = DatumGetRangeTypeP(fc_newentry->key);
	TypeCacheEntry *fc_typcache;
	bool		fc_has_subtype_diff;
	RangeBound	fc_orig_lower,
				fc_new_lower,
				fc_orig_upper,
				fc_new_upper;
	bool		fc_orig_empty,
				fc_new_empty;

	if (RangeTypeGetOid(fc_orig) != RangeTypeGetOid(fc_new))
		elog(ERROR, "range types do not match");

	fc_typcache = range_get_typcache(fcinfo, RangeTypeGetOid(fc_orig));

	fc_has_subtype_diff = OidIsValid(fc_typcache->rng_subdiff_finfo.fn_oid);

	range_deserialize(fc_typcache, fc_orig, &fc_orig_lower, &fc_orig_upper, &fc_orig_empty);
	range_deserialize(fc_typcache, fc_new, &fc_new_lower, &fc_new_upper, &fc_new_empty);

	/*
	 * 处理不同范围类的不同分支。注意，惩罚值只有在相同类别的新范围
	 * 内需要是相称的。
	 */
	if (fc_new_empty)
	{
		/* 处理空范围的插入 */
		if (fc_orig_empty)
		{
			/*
			 * 最理想的情况是将其插入到空的原始范围中。
			 * 在这里插入意味着不会扩大原始范围。此外
			 * 原始范围是最窄的。
			 */
			*fc_penalty = 0.0;
		}
		else if (RangeIsOrContainsEmpty(fc_orig))
		{
			/*
			 * 第二种情况是将空范围插入包含至少一个底层空范围的范围中。
			 * 此时仍然不会扩大原始范围，但原始范围没有尽可能窄。
			 */
			*fc_penalty = CONTAIN_EMPTY_PENALTY;
		}
		else if (fc_orig_lower.infinite && fc_orig_upper.infinite)
		{
			/*
			 * 原始范围需要扩大。(-inf; +inf) 在这种情况下最远
			 * 离正常范围。
			 */
			*fc_penalty = 2 * CONTAIN_EMPTY_PENALTY;
		}
		else if (fc_orig_lower.infinite || fc_orig_upper.infinite)
		{
			/*
			 * (-inf, x) 或 (x, +inf) 原始范围更接近正常
			 * 范围，因此将其与空范围混合会更糟。
			 */
			*fc_penalty = 3 * CONTAIN_EMPTY_PENALTY;
		}
		else
		{
			/*
			 * 最不理想的情况是扩大正常范围。
			 */
			*fc_penalty = 4 * CONTAIN_EMPTY_PENALTY;
		}
	}
	else if (fc_new_lower.infinite && fc_new_upper.infinite)
	{
		/* 处理 (-inf, +inf) 范围的插入 */
		if (fc_orig_lower.infinite && fc_orig_upper.infinite)
		{
			/*
			 * 最佳情况是将其插入到 (-inf, +inf) 原始范围中。
			 */
			*fc_penalty = 0.0;
		}
		else if (fc_orig_lower.infinite || fc_orig_upper.infinite)
		{
			/*
			 * 当原始范围为 (-inf, x) 或 (x, +inf) 时，它需要
			 * 扩大原始范围（一个边界延伸到
			 * 无穷大）。
			 */
			*fc_penalty = INFINITE_BOUND_PENALTY;
		}
		else
		{
			/*
			 * 插入到正常原始范围的情况最不理想。
			 */
			*fc_penalty = 2 * INFINITE_BOUND_PENALTY;
		}

		if (RangeIsOrContainsEmpty(fc_orig))
		{
			/*
			 * 当原始范围不包含空范围时，它更窄。
			 * 否则添加额外的惩罚。
			 */
			*fc_penalty += CONTAIN_EMPTY_PENALTY;
		}
	}
	else if (fc_new_lower.infinite)
	{
		/* 处理 (-inf, x) 范围的插入 */
		if (!fc_orig_empty && fc_orig_lower.infinite)
		{
			if (fc_orig_upper.infinite)
			{
				/*
				 * 插入 (-inf, x) 范围不会扩展 (-inf, +inf) 范围。
				 * 这是一个不太理想的情况，比无扩展地插入
				 * (-inf, y) 原始范围要差，因为在那种情况下
				 * 原始范围更窄。但我们不能用一个浮点值来表示这一点。
				 */
				*fc_penalty = 0.0;
			}
			else
			{
				if (range_cmp_bounds(fc_typcache, &fc_new_upper, &fc_orig_upper) > 0)
				{
					/*
					 * 通过subtype_diff获取原范围的扩展。如果subtype_diff不可用，使用常量。
					 */
					if (fc_has_subtype_diff)
						*fc_penalty = fc_call_subtype_diff(fc_typcache,
													 fc_new_upper.val,
													 fc_orig_upper.val);
					else
						*fc_penalty = DEFAULT_SUBTYPE_DIFF_PENALTY;
				}
				else
				{
					/* 原范围没有扩展 */
					*fc_penalty = 0.0;
				}
			}
		}
		else
		{
			/*
			 * 如果原范围的下界不是-inf，那么它的扩展是无穷大。
			 */
			*fc_penalty = get_float4_infinity();
		}
	}
	else if (fc_new_upper.infinite)
	{
		/* 处理插入(x, +inf)范围 */
		if (!fc_orig_empty && fc_orig_upper.infinite)
		{
			if (fc_orig_lower.infinite)
			{
				/*
				 * (-inf, +inf)范围不会被插入(x, +inf)范围扩展。这比插入(y, +inf)原范围而不扩展的情况更不理想，因为在那种情况下，原范围更狭窄。但是我们无法用单个浮点值表达这一点。
				 */
				*fc_penalty = 0.0;
			}
			else
			{
				if (range_cmp_bounds(fc_typcache, &fc_new_lower, &fc_orig_lower) < 0)
				{
					/*
					 * 通过subtype_diff获取原范围的扩展。如果subtype_diff不可用，使用常量。
					 */
					if (fc_has_subtype_diff)
						*fc_penalty = fc_call_subtype_diff(fc_typcache,
													 fc_orig_lower.val,
													 fc_new_lower.val);
					else
						*fc_penalty = DEFAULT_SUBTYPE_DIFF_PENALTY;
				}
				else
				{
					/* 原范围没有扩展 */
					*fc_penalty = 0.0;
				}
			}
		}
		else
		{
			/*
			 * 如果原范围的上界不是+inf，那么它的扩展是无穷大。
			 */
			*fc_penalty = get_float4_infinity();
		}
	}
	else
	{
		/* 处理插入正常（非空，非无限）范围 */
		if (fc_orig_empty || fc_orig_lower.infinite || fc_orig_upper.infinite)
		{
			/*
			 * 避免将正常范围与无限和空范围混合。
			 */
			*fc_penalty = get_float4_infinity();
		}
		else
		{
			/*
			 * 通过调用subtype_diff计算原范围的扩展。如果subtype_diff不可用，使用常量。
			 */
			float8		fc_diff = 0.0;

			if (range_cmp_bounds(fc_typcache, &fc_new_lower, &fc_orig_lower) < 0)
			{
				if (fc_has_subtype_diff)
					fc_diff += fc_call_subtype_diff(fc_typcache,
											  fc_orig_lower.val,
											  fc_new_lower.val);
				else
					fc_diff += DEFAULT_SUBTYPE_DIFF_PENALTY;
			}
			if (range_cmp_bounds(fc_typcache, &fc_new_upper, &fc_orig_upper) > 0)
			{
				if (fc_has_subtype_diff)
					fc_diff += fc_call_subtype_diff(fc_typcache,
											  fc_new_upper.val,
											  fc_orig_upper.val);
				else
					fc_diff += DEFAULT_SUBTYPE_DIFF_PENALTY;
			}
			*fc_penalty = fc_diff;
		}
	}

	PG_RETURN_POINTER(fc_penalty);
}

/*
 * 用于范围的GiST PickSplit方法
 *
 * 首先，我们尝试将不同类别的范围分隔开。如果是相同类别的范围，则使用该类别的适当分割方法。
 */
Datum range_gist_picksplit(PG_FUNCTION_ARGS)
{
	GistEntryVector *fc_entryvec = (GistEntryVector *) PG_GETARG_POINTER(0);
	GIST_SPLITVEC *fc_v = (GIST_SPLITVEC *) PG_GETARG_POINTER(1);
	TypeCacheEntry *fc_typcache;
	OffsetNumber fc_i;
	RangeType  *fc_pred_left;
	int			fc_nbytes;
	OffsetNumber fc_maxoff;
	int			fc_count_in_classes[CLS_COUNT];
	int			fc_j;
	int			fc_non_empty_classes_count = 0;
	int			fc_biggest_class = -1;
	int			fc_biggest_class_count = 0;
	int			fc_total_count;

	/* 使用第一个项目查找范围类型的信息 */
	fc_pred_left = DatumGetRangeTypeP(fc_entryvec->vector[FirstOffsetNumber].key);
	fc_typcache = range_get_typcache(fcinfo, RangeTypeGetOid(fc_pred_left));

	fc_maxoff = fc_entryvec->n - 1;
	fc_nbytes = (fc_maxoff + 1) * sizeof(OffsetNumber);
	fc_v->spl_left = (OffsetNumber *) palloc(fc_nbytes);
	fc_v->spl_right = (OffsetNumber *) palloc(fc_nbytes);

	/*
	 * 获取范围类别的计数分布。
	 */
	memset(fc_count_in_classes, 0, sizeof(fc_count_in_classes));
	for (fc_i = FirstOffsetNumber; fc_i <= fc_maxoff; fc_i = OffsetNumberNext(fc_i))
	{
		RangeType  *fc_range = DatumGetRangeTypeP(fc_entryvec->vector[fc_i].key);

		fc_count_in_classes[get_gist_range_class(fc_range)]++;
	}

	/*
	 * 计数非空类别并找出最大类别。
	 */
	fc_total_count = fc_maxoff;
	for (fc_j = 0; fc_j < CLS_COUNT; fc_j++)
	{
		if (fc_count_in_classes[fc_j] > 0)
		{
			if (fc_count_in_classes[fc_j] > fc_biggest_class_count)
			{
				fc_biggest_class_count = fc_count_in_classes[fc_j];
				fc_biggest_class = fc_j;
			}
			fc_non_empty_classes_count++;
		}
	}

	Assert(fc_non_empty_classes_count > 0);

	if (fc_non_empty_classes_count == 1)
	{
		/* 一个非空类别，因此在类别内分割 */
		if ((fc_biggest_class & ~CLS_CONTAIN_EMPTY) == CLS_NORMAL)
		{
			/* 普通范围的双重排序分割 */
			fc_range_gist_double_sorting_split(fc_typcache, fc_entryvec, fc_v);
		}
		else if ((fc_biggest_class & ~CLS_CONTAIN_EMPTY) == CLS_LOWER_INF)
		{
			/* (-inf, x)范围的上界排序分割 */
			fc_range_gist_single_sorting_split(fc_typcache, fc_entryvec, fc_v, true);
		}
		else if ((fc_biggest_class & ~CLS_CONTAIN_EMPTY) == CLS_UPPER_INF)
		{
			/* (x, +inf)范围的下界排序分割 */
			fc_range_gist_single_sorting_split(fc_typcache, fc_entryvec, fc_v, false);
		}
		else
		{
			/* 所有(-inf, +inf)或所有空范围的微不足道的分割 */
			fc_range_gist_fallback_split(fc_typcache, fc_entryvec, fc_v);
		}
	}
	else
	{
		/*
		 * 基于类别的分割。
		 *
		 * 每个类别应该去分割的哪一侧？ 初始化它们都去左侧。
		 */
		SplitLR		fc_classes_groups[CLS_COUNT];

		memset(fc_classes_groups, 0, sizeof(fc_classes_groups));

		if (fc_count_in_classes[CLS_NORMAL] > 0)
		{
			/* 如果有的话，分开正常范围 */
			fc_classes_groups[CLS_NORMAL] = SPLIT_RIGHT;
		}
		else
		{
			/*----------
			 * 尝试以两种方式分割类别：
			 *	1) 包含无穷大 - 不包含无穷大
			 *	2) 包含空 - 不包含空
			 *
			 * 选择最佳地平衡左右范围的方式。如果以这些方式进行分割不可能，那么最多有3个类别，因此只需分开最大的类别即可。
			 *----------
			 */
			int			fc_infCount,
						fc_nonInfCount;
			int			fc_emptyCount,
						fc_nonEmptyCount;

			fc_nonInfCount =
				fc_count_in_classes[CLS_NORMAL] +
				fc_count_in_classes[CLS_CONTAIN_EMPTY] +
				fc_count_in_classes[CLS_EMPTY];
			fc_infCount = fc_total_count - fc_nonInfCount;

			fc_nonEmptyCount =
				fc_count_in_classes[CLS_NORMAL] +
				fc_count_in_classes[CLS_LOWER_INF] +
				fc_count_in_classes[CLS_UPPER_INF] +
				fc_count_in_classes[CLS_LOWER_INF | CLS_UPPER_INF];
			fc_emptyCount = fc_total_count - fc_nonEmptyCount;

			if (fc_infCount > 0 && fc_nonInfCount > 0 &&
				(Abs(fc_infCount - fc_nonInfCount) <=
				 Abs(fc_emptyCount - fc_nonEmptyCount)))
			{
				fc_classes_groups[CLS_NORMAL] = SPLIT_RIGHT;
				fc_classes_groups[CLS_CONTAIN_EMPTY] = SPLIT_RIGHT;
				fc_classes_groups[CLS_EMPTY] = SPLIT_RIGHT;
			}
			else if (fc_emptyCount > 0 && fc_nonEmptyCount > 0)
			{
				fc_classes_groups[CLS_NORMAL] = SPLIT_RIGHT;
				fc_classes_groups[CLS_LOWER_INF] = SPLIT_RIGHT;
				fc_classes_groups[CLS_UPPER_INF] = SPLIT_RIGHT;
				fc_classes_groups[CLS_LOWER_INF | CLS_UPPER_INF] = SPLIT_RIGHT;
			}
			else
			{
				/*
				 * 要么total_count == emptyCount，要么total_count == infCount。
				 */
				fc_classes_groups[fc_biggest_class] = SPLIT_RIGHT;
			}
		}

		fc_range_gist_class_split(fc_typcache, fc_entryvec, fc_v, fc_classes_groups);
	}

	PG_RETURN_POINTER(fc_v);
}

/* GiST的相等比较器 */
Datum range_gist_same(PG_FUNCTION_ARGS)
{
	RangeType  *fc_r1 = PG_GETARG_RANGE_P(0);
	RangeType  *fc_r2 = PG_GETARG_RANGE_P(1);
	bool	   *fc_result = (bool *) PG_GETARG_POINTER(2);

	/*
	 * range_eq将忽略RANGE_CONTAIN_EMPTY标志，因此我们必须自己检查这一点。更一般来说，如果条目已经被正确规范化，那么不相等的标志字节必须意味着不相等的范围……所以让我们一次测试所有的标志位。
	 */
	if (range_get_flags(fc_r1) != range_get_flags(fc_r2))
		*fc_result = false;
	else
	{
		TypeCacheEntry *fc_typcache;

		fc_typcache = range_get_typcache(fcinfo, RangeTypeGetOid(fc_r1));

		*fc_result = range_eq_internal(fc_typcache, fc_r1, fc_r2);
	}

	PG_RETURN_POINTER(fc_result);
}

/*
 *----------------------------------------------------------
 * 静态函数
 *----------------------------------------------------------
 */

/*
 * 返回包含r1和r2的最小范围
 *
 * 这与常规的range_union在两个关键方面有所不同：
 * 1. 它不会因r1和r2不相邻而抛出错误，而只是将介于两者之间的值吸收进结果范围。
 * 2. 我们跟踪是否有任何空范围已被加入到结果中，以便包含搜索可以被索引。请注意，这意味着在GiST索引中形成的*所有*联合都必须通过此处。
 */
static RangeType *
fc_range_super_union(TypeCacheEntry *fc_typcache, RangeType *fc_r1, RangeType *fc_r2)
{
	RangeType  *fc_result;
	RangeBound	fc_lower1,
				fc_lower2;
	RangeBound	fc_upper1,
				fc_upper2;
	bool		fc_empty1,
				fc_empty2;
	char		fc_flags1,
				fc_flags2;
	RangeBound *fc_result_lower;
	RangeBound *fc_result_upper;

	range_deserialize(fc_typcache, fc_r1, &fc_lower1, &fc_upper1, &fc_empty1);
	range_deserialize(fc_typcache, fc_r2, &fc_lower2, &fc_upper2, &fc_empty2);
	fc_flags1 = range_get_flags(fc_r1);
	fc_flags2 = range_get_flags(fc_r2);

	if (fc_empty1)
	{
		/* 如果r2已经是或包含空值，我们可以直接返回r2 */
		if (fc_flags2 & (RANGE_EMPTY | RANGE_CONTAIN_EMPTY))
			return fc_r2;
		/* 否则，我们最好复制它（就地修改不安全） */
		fc_r2 = rangeCopy(fc_r2);
		range_set_contain_empty(fc_r2);
		return fc_r2;
	}
	if (fc_empty2)
	{
		/* 如果r1已经是或包含空值，我们可以直接返回r1 */
		if (fc_flags1 & (RANGE_EMPTY | RANGE_CONTAIN_EMPTY))
			return fc_r1;
		/* 否则，我们最好复制它（就地修改不安全） */
		fc_r1 = rangeCopy(fc_r1);
		range_set_contain_empty(fc_r1);
		return fc_r1;
	}

	if (range_cmp_bounds(fc_typcache, &fc_lower1, &fc_lower2) <= 0)
		fc_result_lower = &fc_lower1;
	else
		fc_result_lower = &fc_lower2;

	if (range_cmp_bounds(fc_typcache, &fc_upper1, &fc_upper2) >= 0)
		fc_result_upper = &fc_upper1;
	else
		fc_result_upper = &fc_upper2;

	/* 优化以避免构造新范围 */
	if (fc_result_lower == &fc_lower1 && fc_result_upper == &fc_upper1 &&
		((fc_flags1 & RANGE_CONTAIN_EMPTY) || !(fc_flags2 & RANGE_CONTAIN_EMPTY)))
		return fc_r1;
	if (fc_result_lower == &fc_lower2 && fc_result_upper == &fc_upper2 &&
		((fc_flags2 & RANGE_CONTAIN_EMPTY) || !(fc_flags1 & RANGE_CONTAIN_EMPTY)))
		return fc_r2;

	fc_result = make_range(fc_typcache, fc_result_lower, fc_result_upper, false);

	if ((fc_flags1 & RANGE_CONTAIN_EMPTY) || (fc_flags2 & RANGE_CONTAIN_EMPTY))
		range_set_contain_empty(fc_result);

	return fc_result;
}

static bool fc_multirange_union_range_equal(TypeCacheEntry *fc_typcache,
							 const RangeType *fc_r,
							 const MultirangeType *fc_mr)
{
	RangeBound	fc_lower1,
				fc_upper1,
				fc_lower2,
				fc_upper2,
				fc_tmp;
	bool		fc_empty;

	if (RangeIsEmpty(fc_r) || MultirangeIsEmpty(fc_mr))
		return (RangeIsEmpty(fc_r) && MultirangeIsEmpty(fc_mr));

	range_deserialize(fc_typcache, fc_r, &fc_lower1, &fc_upper1, &fc_empty);
	Assert(!fc_empty);
	multirange_get_bounds(fc_typcache, fc_mr, 0, &fc_lower2, &fc_tmp);
	multirange_get_bounds(fc_typcache, fc_mr, fc_mr->rangeCount - 1, &fc_tmp, &fc_upper2);

	return (range_cmp_bounds(fc_typcache, &fc_lower1, &fc_lower2) == 0 &&
			range_cmp_bounds(fc_typcache, &fc_upper1, &fc_upper2) == 0);
}

/*
 * 基于范围查询的索引内部页面上的GiST一致性测试
 */
static bool fc_range_gist_consistent_int_range(TypeCacheEntry *fc_typcache,
								StrategyNumber fc_strategy,
								const RangeType *fc_key,
								const RangeType *fc_query)
{
	switch (fc_strategy)
	{
		case RANGESTRAT_BEFORE:
			if (RangeIsEmpty(fc_key) || RangeIsEmpty(fc_query))
				return false;
			return (!range_overright_internal(fc_typcache, fc_key, fc_query));
		case RANGESTRAT_OVERLEFT:
			if (RangeIsEmpty(fc_key) || RangeIsEmpty(fc_query))
				return false;
			return (!range_after_internal(fc_typcache, fc_key, fc_query));
		case RANGESTRAT_OVERLAPS:
			return range_overlaps_internal(fc_typcache, fc_key, fc_query);
		case RANGESTRAT_OVERRIGHT:
			if (RangeIsEmpty(fc_key) || RangeIsEmpty(fc_query))
				return false;
			return (!range_before_internal(fc_typcache, fc_key, fc_query));
		case RANGESTRAT_AFTER:
			if (RangeIsEmpty(fc_key) || RangeIsEmpty(fc_query))
				return false;
			return (!range_overleft_internal(fc_typcache, fc_key, fc_query));
		case RANGESTRAT_ADJACENT:
			if (RangeIsEmpty(fc_key) || RangeIsEmpty(fc_query))
				return false;
			if (range_adjacent_internal(fc_typcache, fc_key, fc_query))
				return true;
			return range_overlaps_internal(fc_typcache, fc_key, fc_query);
		case RANGESTRAT_CONTAINS:
			return range_contains_internal(fc_typcache, fc_key, fc_query);
		case RANGESTRAT_CONTAINED_BY:

			/*
			 * 空区间可以被任何东西包含，因此如果键是或包含任何空区间，
			 * 我们必须向下遍历。否则，仅在键与查询重叠时向下遍历。
			 */
			if (RangeIsOrContainsEmpty(fc_key))
				return true;
			return range_overlaps_internal(fc_typcache, fc_key, fc_query);
		case RANGESTRAT_EQ:

			/*
			 * 如果查询为空，仅在键是或包含任何空区间时向下遍历。
			 * 否则，在键包含查询时向下遍历。
			 */
			if (RangeIsEmpty(fc_query))
				return RangeIsOrContainsEmpty(fc_key);
			return range_contains_internal(fc_typcache, fc_key, fc_query);
		default:
			elog(ERROR, "unrecognized range strategy: %d", fc_strategy);
			return false;		/* 保持编译器安静 */
	}
}

/*
 * GiST 在带有多范围查询的索引内部页面上进行一致性测试
 */
static bool fc_range_gist_consistent_int_multirange(TypeCacheEntry *fc_typcache,
									 StrategyNumber fc_strategy,
									 const RangeType *fc_key,
									 const MultirangeType *fc_query)
{
	switch (fc_strategy)
	{
		case RANGESTRAT_BEFORE:
			if (RangeIsEmpty(fc_key) || MultirangeIsEmpty(fc_query))
				return false;
			return (!range_overright_multirange_internal(fc_typcache, fc_key, fc_query));
		case RANGESTRAT_OVERLEFT:
			if (RangeIsEmpty(fc_key) || MultirangeIsEmpty(fc_query))
				return false;
			return (!range_after_multirange_internal(fc_typcache, fc_key, fc_query));
		case RANGESTRAT_OVERLAPS:
			return range_overlaps_multirange_internal(fc_typcache, fc_key, fc_query);
		case RANGESTRAT_OVERRIGHT:
			if (RangeIsEmpty(fc_key) || MultirangeIsEmpty(fc_query))
				return false;
			return (!range_before_multirange_internal(fc_typcache, fc_key, fc_query));
		case RANGESTRAT_AFTER:
			if (RangeIsEmpty(fc_key) || MultirangeIsEmpty(fc_query))
				return false;
			return (!range_overleft_multirange_internal(fc_typcache, fc_key, fc_query));
		case RANGESTRAT_ADJACENT:
			if (RangeIsEmpty(fc_key) || MultirangeIsEmpty(fc_query))
				return false;
			if (range_adjacent_multirange_internal(fc_typcache, fc_key, fc_query))
				return true;
			return range_overlaps_multirange_internal(fc_typcache, fc_key, fc_query);
		case RANGESTRAT_CONTAINS:
			return range_contains_multirange_internal(fc_typcache, fc_key, fc_query);
		case RANGESTRAT_CONTAINED_BY:

			/*
			 * 空区间可以被任何东西包含，因此如果键是或包含任何空区间，
			 * 我们必须向下遍历。否则，仅在键与查询重叠时向下遍历。
			 */
			if (RangeIsOrContainsEmpty(fc_key))
				return true;
			return range_overlaps_multirange_internal(fc_typcache, fc_key, fc_query);
		case RANGESTRAT_EQ:

			/*
			 * 如果查询为空，仅在键是或包含任何空区间时向下遍历。
			 * 否则，在键包含查询时向下遍历。
			 */
			if (MultirangeIsEmpty(fc_query))
				return RangeIsOrContainsEmpty(fc_key);
			return range_contains_multirange_internal(fc_typcache, fc_key, fc_query);
		default:
			elog(ERROR, "unrecognized range strategy: %d", fc_strategy);
			return false;		/* 保持编译器安静 */
	}
}

/*
 * GiST 在带有元素查询的索引内部页面上进行一致性测试
 */
static bool fc_range_gist_consistent_int_element(TypeCacheEntry *fc_typcache,
								  StrategyNumber fc_strategy,
								  const RangeType *fc_key,
								  Datum fc_query)
{
	switch (fc_strategy)
	{
		case RANGESTRAT_CONTAINS_ELEM:
			return range_contains_elem_internal(fc_typcache, fc_key, fc_query);
		default:
			elog(ERROR, "unrecognized range strategy: %d", fc_strategy);
			return false;		/* 保持编译器安静 */
	}
}

/*
 * GiST 在带有范围查询的索引叶子页面上进行一致性测试
 */
static bool fc_range_gist_consistent_leaf_range(TypeCacheEntry *fc_typcache,
								 StrategyNumber fc_strategy,
								 const RangeType *fc_key,
								 const RangeType *fc_query)
{
	switch (fc_strategy)
	{
		case RANGESTRAT_BEFORE:
			return range_before_internal(fc_typcache, fc_key, fc_query);
		case RANGESTRAT_OVERLEFT:
			return range_overleft_internal(fc_typcache, fc_key, fc_query);
		case RANGESTRAT_OVERLAPS:
			return range_overlaps_internal(fc_typcache, fc_key, fc_query);
		case RANGESTRAT_OVERRIGHT:
			return range_overright_internal(fc_typcache, fc_key, fc_query);
		case RANGESTRAT_AFTER:
			return range_after_internal(fc_typcache, fc_key, fc_query);
		case RANGESTRAT_ADJACENT:
			return range_adjacent_internal(fc_typcache, fc_key, fc_query);
		case RANGESTRAT_CONTAINS:
			return range_contains_internal(fc_typcache, fc_key, fc_query);
		case RANGESTRAT_CONTAINED_BY:
			return range_contained_by_internal(fc_typcache, fc_key, fc_query);
		case RANGESTRAT_EQ:
			return range_eq_internal(fc_typcache, fc_key, fc_query);
		default:
			elog(ERROR, "unrecognized range strategy: %d", fc_strategy);
			return false;		/* 保持编译器安静 */
	}
}

/*
 * GiST 在带有多范围查询的索引叶子页面上进行一致性测试
 */
static bool fc_range_gist_consistent_leaf_multirange(TypeCacheEntry *fc_typcache,
									  StrategyNumber fc_strategy,
									  const RangeType *fc_key,
									  const MultirangeType *fc_query)
{
	switch (fc_strategy)
	{
		case RANGESTRAT_BEFORE:
			return range_before_multirange_internal(fc_typcache, fc_key, fc_query);
		case RANGESTRAT_OVERLEFT:
			return range_overleft_multirange_internal(fc_typcache, fc_key, fc_query);
		case RANGESTRAT_OVERLAPS:
			return range_overlaps_multirange_internal(fc_typcache, fc_key, fc_query);
		case RANGESTRAT_OVERRIGHT:
			return range_overright_multirange_internal(fc_typcache, fc_key, fc_query);
		case RANGESTRAT_AFTER:
			return range_after_multirange_internal(fc_typcache, fc_key, fc_query);
		case RANGESTRAT_ADJACENT:
			return range_adjacent_multirange_internal(fc_typcache, fc_key, fc_query);
		case RANGESTRAT_CONTAINS:
			return range_contains_multirange_internal(fc_typcache, fc_key, fc_query);
		case RANGESTRAT_CONTAINED_BY:
			return multirange_contains_range_internal(fc_typcache, fc_query, fc_key);
		case RANGESTRAT_EQ:
			return fc_multirange_union_range_equal(fc_typcache, fc_key, fc_query);
		default:
			elog(ERROR, "unrecognized range strategy: %d", fc_strategy);
			return false;		/* 保持编译器安静 */
	}
}

/*
 * GiST 在带有元素查询的索引叶子页面上进行一致性测试
 */
static bool fc_range_gist_consistent_leaf_element(TypeCacheEntry *fc_typcache,
								   StrategyNumber fc_strategy,
								   const RangeType *fc_key,
								   Datum fc_query)
{
	switch (fc_strategy)
	{
		case RANGESTRAT_CONTAINS_ELEM:
			return range_contains_elem_internal(fc_typcache, fc_key, fc_query);
		default:
			elog(ERROR, "unrecognized range strategy: %d", fc_strategy);
			return false;		/* 保持编译器安静 */
	}
}

/*
 * 微不足道的分割：一半的条目将放在一页上，
 * 另一半的条目将放在另一页上。
 */
static void fc_range_gist_fallback_split(TypeCacheEntry *fc_typcache,
						  GistEntryVector *fc_entryvec,
						  GIST_SPLITVEC *fc_v)
{
	RangeType  *fc_left_range = NULL;
	RangeType  *fc_right_range = NULL;
	OffsetNumber fc_i,
				fc_maxoff,
				fc_split_idx;

	fc_maxoff = fc_entryvec->n - 1;
	/* 在此之前将条目分割到左页，之后分割到右页： */
	fc_split_idx = (fc_maxoff - FirstOffsetNumber) / 2 + FirstOffsetNumber;

	fc_v->spl_nleft = 0;
	fc_v->spl_nright = 0;
	for (fc_i = FirstOffsetNumber; fc_i <= fc_maxoff; fc_i++)
	{
		RangeType  *fc_range = DatumGetRangeTypeP(fc_entryvec->vector[fc_i].key);

		if (fc_i < fc_split_idx)
			PLACE_LEFT(fc_range, fc_i);
		else
			PLACE_RIGHT(fc_range, fc_i);
	}

	fc_v->spl_ldatum = RangeTypePGetDatum(fc_left_range);
	fc_v->spl_rdatum = RangeTypePGetDatum(fc_right_range);
}

/*
 * 基于范围类别的分割。
 *
 * 请参见 get_gist_range_class 以获取类别定义。
 * classes_groups 是一个长度为 CLS_COUNT 的数组，指示每个类别
 * 应该去哪个分割边。
 */
static void fc_range_gist_class_split(TypeCacheEntry *fc_typcache,
					   GistEntryVector *fc_entryvec,
					   GIST_SPLITVEC *fc_v,
					   SplitLR *fc_classes_groups)
{
	RangeType  *fc_left_range = NULL;
	RangeType  *fc_right_range = NULL;
	OffsetNumber fc_i,
				fc_maxoff;

	fc_maxoff = fc_entryvec->n - 1;

	fc_v->spl_nleft = 0;
	fc_v->spl_nright = 0;
	for (fc_i = FirstOffsetNumber; fc_i <= fc_maxoff; fc_i = OffsetNumberNext(fc_i))
	{
		RangeType  *fc_range = DatumGetRangeTypeP(fc_entryvec->vector[fc_i].key);
		int			fc_class;

		/* 获取范围的类别 */
		fc_class = get_gist_range_class(fc_range);

		/* 将范围放置到适当的页面 */
		if (fc_classes_groups[fc_class] == SPLIT_LEFT)
			PLACE_LEFT(fc_range, fc_i);
		else
		{
			Assert(fc_classes_groups[fc_class] == SPLIT_RIGHT);
			PLACE_RIGHT(fc_range, fc_i);
		}
	}

	fc_v->spl_ldatum = RangeTypePGetDatum(fc_left_range);
	fc_v->spl_rdatum = RangeTypePGetDatum(fc_right_range);
}

/*
 * 基于排序的分割。根据排序的前半部分条目将
 * 被放置到一页，后半部分条目将被放置到另一页。use_upper_bound 参数指示是否
 * 使用上限或下限进行排序。
 */
static void fc_range_gist_single_sorting_split(TypeCacheEntry *fc_typcache,
								GistEntryVector *fc_entryvec,
								GIST_SPLITVEC *fc_v,
								bool fc_use_upper_bound)
{
	SingleBoundSortItem *fc_sortItems;
	RangeType  *fc_left_range = NULL;
	RangeType  *fc_right_range = NULL;
	OffsetNumber fc_i,
				fc_maxoff,
				fc_split_idx;

	fc_maxoff = fc_entryvec->n - 1;

	fc_sortItems = (SingleBoundSortItem *)
		palloc(fc_maxoff * sizeof(SingleBoundSortItem));

	/*
	 * 准备辅助数组并对值进行排序。
	 */
	for (fc_i = FirstOffsetNumber; fc_i <= fc_maxoff; fc_i = OffsetNumberNext(fc_i))
	{
		RangeType  *fc_range = DatumGetRangeTypeP(fc_entryvec->vector[fc_i].key);
		RangeBound	fc_bound2;
		bool		fc_empty;

		fc_sortItems[fc_i - 1].index = fc_i;
		/* 将适当的边界放入数组中 */
		if (fc_use_upper_bound)
			range_deserialize(fc_typcache, fc_range, &fc_bound2,
							  &fc_sortItems[fc_i - 1].bound, &fc_empty);
		else
			range_deserialize(fc_typcache, fc_range, &fc_sortItems[fc_i - 1].bound,
							  &fc_bound2, &fc_empty);
		Assert(!fc_empty);
	}

	qsort_arg(fc_sortItems, fc_maxoff, sizeof(SingleBoundSortItem),
			  fc_single_bound_cmp, fc_typcache);

	fc_split_idx = fc_maxoff / 2;

	fc_v->spl_nleft = 0;
	fc_v->spl_nright = 0;

	for (fc_i = 0; fc_i < fc_maxoff; fc_i++)
	{
		int			fc_idx = fc_sortItems[fc_i].index;
		RangeType  *fc_range = DatumGetRangeTypeP(fc_entryvec->vector[fc_idx].key);

		if (fc_i < fc_split_idx)
			PLACE_LEFT(fc_range, fc_idx);
		else
			PLACE_RIGHT(fc_range, fc_idx);
	}

	fc_v->spl_ldatum = RangeTypePGetDatum(fc_left_range);
	fc_v->spl_rdatum = RangeTypePGetDatum(fc_right_range);
}

/*
 * 双重排序分割算法。
 *
 * 该算法考虑将范围分为两个组。第一（左）组包含一般左边界。
 * 第二（右）组包含一般右边界。挑战在于找到左组的上边界
 * 和右组的下边界，以便最小化组之间的重叠，并使分布的比例
 * 可接受。算法为右组的每个下边界找到左组的最小上边界，
 * 为左组的每个上边界找到右组的最大下边界。对于每个找到的对
 * range_gist_consider_split 考虑用新的替换当前选择的
 * 分割。
 *
 * 之后，所有条目被分为三组：
 * 1）应该放置到左组的条目
 * 2）应该放置到右组的条目
 * 3）“公共条目”，可以放置到任一组，而不会影响
 *	  重叠的数量。
 *
 * 公共范围根据公共范围的下边界到右组下边界之间的距离
 * 和公共范围的上边界到左组上边界之间的距离进行分配。
 *
 * 详情见：
 * “一种新的基于双重排序的 R 树节点分割算法”，
 * A. Korotkov
 * http://syrcose.ispras.ru/2011/files/SYRCoSE2011_Proceedings.pdf#page=36
 */
static void fc_range_gist_double_sorting_split(TypeCacheEntry *fc_typcache,
								GistEntryVector *fc_entryvec,
								GIST_SPLITVEC *fc_v)
{
	ConsiderSplitContext fc_context;
	OffsetNumber fc_i,
				fc_maxoff;
	RangeType  *fc_range,
			   *fc_left_range = NULL,
			   *fc_right_range = NULL;
	int			fc_common_entries_count;
	NonEmptyRange *fc_by_lower,
			   *fc_by_upper;
	CommonEntry *fc_common_entries;
	int			fc_nentries,
				fc_i1,
				fc_i2;
	RangeBound *fc_right_lower,
			   *fc_left_upper;

	memset(&fc_context, 0, sizeof(ConsiderSplitContext));
	fc_context.typcache = fc_typcache;
	fc_context.has_subtype_diff = OidIsValid(fc_typcache->rng_subdiff_finfo.fn_oid);

	fc_maxoff = fc_entryvec->n - 1;
	fc_nentries = fc_context.entries_count = fc_maxoff - FirstOffsetNumber + 1;
	fc_context.first = true;

	/* 为排序范围的边界分配数组 */
	fc_by_lower = (NonEmptyRange *) palloc(fc_nentries * sizeof(NonEmptyRange));
	fc_by_upper = (NonEmptyRange *) palloc(fc_nentries * sizeof(NonEmptyRange));

	/* 填充边界数组 */
	for (fc_i = FirstOffsetNumber; fc_i <= fc_maxoff; fc_i = OffsetNumberNext(fc_i))
	{
		RangeType  *fc_range = DatumGetRangeTypeP(fc_entryvec->vector[fc_i].key);
		bool		fc_empty;

		range_deserialize(fc_typcache, fc_range,
						  &fc_by_lower[fc_i - FirstOffsetNumber].lower,
						  &fc_by_lower[fc_i - FirstOffsetNumber].upper,
						  &fc_empty);
		Assert(!fc_empty);
	}

	/*
	 * 制作两个范围边界数组：一个按下边界排序，另一个
	 * 按上边界排序。
	 */
	memcpy(fc_by_upper, fc_by_lower, fc_nentries * sizeof(NonEmptyRange));
	qsort_arg(fc_by_lower, fc_nentries, sizeof(NonEmptyRange),
			  fc_interval_cmp_lower, fc_typcache);
	qsort_arg(fc_by_upper, fc_nentries, sizeof(NonEmptyRange),
			  fc_interval_cmp_upper, fc_typcache);

	/*----------
	 * 目标是形成一个左范围和一个右范围，以便每个条目
	 * 范围都被左右任一间隔（或两者）包含。
	 *
	 * 例如，对于范围 (0,1)、(1,3)、(2,3)、(2,4)：
	 *
	 * 0 1 2 3 4
	 * +-+
	 *	 +---+
	 *	   +-+
	 *	   +---+
	 *
	 * 左右范围的形式为 (0,a) 和 (b,4)。
	 * 我们首先考虑 b 是条目的下边界时的分割。
	 * 我们迭代所有条目，对于每个 b，计算最小可能的 a。然后我们考虑 a 是条目的
	 * 上边界时的分割，对于每个 a，计算最大可能的 b。
	 *
	 * 在上面的示例中，第一个循环会考虑分割：
	 * b=0: (0,1)-(0,4)
	 * b=1: (0,1)-(1,4)
	 * b=2: (0,3)-(2,4)
	 *
	 * 而第二个循环：
	 * a=1: (0,1)-(1,4)
	 * a=3: (0,3)-(2,4)
	 * a=4: (0,4)-(2,4)
	 *----------
	 */

	/*
	 * 迭代右组的下边界，找到左组的最小可能
	 * 上边界。
	 */
	fc_i1 = 0;
	fc_i2 = 0;
	fc_right_lower = &fc_by_lower[fc_i1].lower;
	fc_left_upper = &fc_by_upper[fc_i2].lower;
	while (true)
	{
		/*
		 * 找到右组的下一个下边界。
		 */
		while (fc_i1 < fc_nentries &&
			   range_cmp_bounds(fc_typcache, fc_right_lower,
								&fc_by_lower[fc_i1].lower) == 0)
		{
			if (range_cmp_bounds(fc_typcache, &fc_by_lower[fc_i1].upper,
								 fc_left_upper) > 0)
				fc_left_upper = &fc_by_lower[fc_i1].upper;
			fc_i1++;
		}
		if (fc_i1 >= fc_nentries)
			break;
		fc_right_lower = &fc_by_lower[fc_i1].lower;

		/*
		 * 找到无论如何应该放置到左组的范围计数。
		 */
		while (fc_i2 < fc_nentries &&
			   range_cmp_bounds(fc_typcache, &fc_by_upper[fc_i2].upper,
								fc_left_upper) <= 0)
			fc_i2++;

		/*
		 * 考虑找到的分割，看看它是否比我们已有的更好。
		 */
		fc_range_gist_consider_split(&fc_context, fc_right_lower, fc_i1, fc_left_upper, fc_i2);
	}

	/*
	 * 迭代左组的上边界，找到右组的最大可能下
	 * 边界。
	 */
	fc_i1 = fc_nentries - 1;
	fc_i2 = fc_nentries - 1;
	fc_right_lower = &fc_by_lower[fc_i1].upper;
	fc_left_upper = &fc_by_upper[fc_i2].upper;
	while (true)
	{
		/*
		 * 找到左组的下一个上边界。
		 */
		while (fc_i2 >= 0 &&
			   range_cmp_bounds(fc_typcache, fc_left_upper,
								&fc_by_upper[fc_i2].upper) == 0)
		{
			if (range_cmp_bounds(fc_typcache, &fc_by_upper[fc_i2].lower,
								 fc_right_lower) < 0)
				fc_right_lower = &fc_by_upper[fc_i2].lower;
			fc_i2--;
		}
		if (fc_i2 < 0)
			break;
		fc_left_upper = &fc_by_upper[fc_i2].upper;

		/*
		 * 找到无论如何应该放置到右组的区间数量。
		 */
		while (fc_i1 >= 0 &&
			   range_cmp_bounds(fc_typcache, &fc_by_lower[fc_i1].lower,
								fc_right_lower) >= 0)
			fc_i1--;

		/*
		 * 考虑找到的分割，看看它是否比我们已有的更好。
		 */
		fc_range_gist_consider_split(&fc_context, fc_right_lower, fc_i1 + 1,
								  fc_left_upper, fc_i2 + 1);
	}

	/*
	 * 如果我们未能找到任何可接受的分裂，使用简单的分裂。
	 */
	if (fc_context.first)
	{
		fc_range_gist_fallback_split(fc_typcache, fc_entryvec, fc_v);
		return;
	}

	/*
	 * 好的，我们现在已经选择了组的边界。现在我们必须
	 * 分配条目本身。起初我们分配那些可以
	 * 明确放置的条目，并将“公共条目”收集到数组中。
	 */

	/* 为结果分配向量 */
	fc_v->spl_left = (OffsetNumber *) palloc(fc_nentries * sizeof(OffsetNumber));
	fc_v->spl_right = (OffsetNumber *) palloc(fc_nentries * sizeof(OffsetNumber));
	fc_v->spl_nleft = 0;
	fc_v->spl_nright = 0;

	/*
	 * 为“公共条目”分配一个数组 - 可以放置到任一组而不影响所选轴上的重叠的条目。
	 */
	fc_common_entries_count = 0;
	fc_common_entries = (CommonEntry *) palloc(fc_nentries * sizeof(CommonEntry));

	/*
	 * 分配可以明确分配的条目，并收集公共条目。
	 */
	for (fc_i = FirstOffsetNumber; fc_i <= fc_maxoff; fc_i = OffsetNumberNext(fc_i))
	{
		RangeBound	fc_lower,
					fc_upper;
		bool		fc_empty;

		/*
		 * 获取所选轴上的上限和下限。
		 */
		fc_range = DatumGetRangeTypeP(fc_entryvec->vector[fc_i].key);

		range_deserialize(fc_typcache, fc_range, &fc_lower, &fc_upper, &fc_empty);

		if (range_cmp_bounds(fc_typcache, &fc_upper, fc_context.left_upper) <= 0)
		{
			
/* 适合左组 */
			if (range_cmp_bounds(fc_typcache, &fc_lower, fc_context.right_lower) >= 0)
			{
				/* 也适合右组，因此是“公共入口” */
				fc_common_entries[fc_common_entries_count].index = fc_i;
				if (fc_context.has_subtype_diff)
				{
					/*
					 * delta = (lower - context.right_lower) -
					 * (context.left_upper - upper)
					 */
					fc_common_entries[fc_common_entries_count].delta =
						fc_call_subtype_diff(fc_typcache,
										  fc_lower.val,
										  fc_context.right_lower->val) -
						fc_call_subtype_diff(fc_typcache,
										  fc_context.left_upper->val,
										  fc_upper.val);
				}
				else
				{
					/* 没有 subtype_diff，所有增量视为零 */
					fc_common_entries[fc_common_entries_count].delta = 0;
				}
				fc_common_entries_count++;
			}
			else
			{
				/* 不适合右组，因此加入左组 */
				PLACE_LEFT(fc_range, fc_i);
			}
		}
		else
		{
			/*
			 * 每个条目应该适合于左组或右组。由于该条目未适合左组，因此最好适合右组。
			 */
			Assert(range_cmp_bounds(fc_typcache, &fc_lower,
									fc_context.right_lower) >= 0);
			PLACE_RIGHT(fc_range, fc_i);
		}
	}

	/*
	 * 分配“公共条目”，如果有的话。
	 */
	if (fc_common_entries_count > 0)
	{
		/*
		 * 按计算出的差值对“公共条目”进行排序，以优先分配最模糊的条目。
		 */
		qsort(fc_common_entries, fc_common_entries_count, sizeof(CommonEntry),
			  fc_common_entry_cmp);

		/*
		 * 根据排序在组之间分配“公共条目”。
		 */
		for (fc_i = 0; fc_i < fc_common_entries_count; fc_i++)
		{
			int			fc_idx = fc_common_entries[fc_i].index;

			fc_range = DatumGetRangeTypeP(fc_entryvec->vector[fc_idx].key);

			/*
			 * 检查我们是否必须将此条目放置到任一组中，以达到LIMIT_RATIO。
			 */
			if (fc_i < fc_context.common_left)
				PLACE_LEFT(fc_range, fc_idx);
			else
				PLACE_RIGHT(fc_range, fc_idx);
		}
	}

	fc_v->spl_ldatum = PointerGetDatum(fc_left_range);
	fc_v->spl_rdatum = PointerGetDatum(fc_right_range);
}

/*
 * 考虑在 range_gist_double_sorting_split 期间用更好的分割替代当前选择的分割。
 */
static void fc_range_gist_consider_split(ConsiderSplitContext *fc_context,
						  RangeBound *fc_right_lower, int fc_min_left_count,
						  RangeBound *fc_left_upper, int fc_max_left_count)
{
	int			fc_left_count,
				fc_right_count;
	float4		fc_ratio,
				fc_overlap;

	/*
	 * 计算条目分布比率，假设公共条目的分布最为均匀。
	 */
	if (fc_min_left_count >= (fc_context->entries_count + 1) / 2)
		fc_left_count = fc_min_left_count;
	else if (fc_max_left_count <= fc_context->entries_count / 2)
		fc_left_count = fc_max_left_count;
	else
		fc_left_count = fc_context->entries_count / 2;
	fc_right_count = fc_context->entries_count - fc_left_count;

	/*
	 * 分割的比例：较小组的大小与总条目数的商。这必然是0.5或更小；如果小于 LIMIT_RATIO，那么我们将永远不会接受新的分割。
	 */
	fc_ratio = ((float4) Min(fc_left_count, fc_right_count)) /
		((float4) fc_context->entries_count);

	if (fc_ratio > LIMIT_RATIO)
	{
		bool		fc_selectthis = false;

		/*
		 * 比例是可接受的，因此将当前分割与之前选择的进行比较。我们搜索最小重叠（允许负值）和最小比例。 如果 subtype_diff 可用，它将用于重叠度量。没有 subtype_diff，我们使用“公共条目”的数量作为重叠度量。
		 */
		if (fc_context->has_subtype_diff)
			fc_overlap = fc_call_subtype_diff(fc_context->typcache,
										fc_left_upper->val,
										fc_right_lower->val);
		else
			fc_overlap = fc_max_left_count - fc_min_left_count;

		/* 如果没有之前的选择，选择这个分割 */
		if (fc_context->first)
			fc_selectthis = true;
		else
		{
			/*
			 * 如果新分割的重叠更小，或重叠相同但比例更好，则选择新分割。
			 */
			if (fc_overlap < fc_context->overlap ||
				(fc_overlap == fc_context->overlap && fc_ratio > fc_context->ratio))
				fc_selectthis = true;
		}

		if (fc_selectthis)
		{
			/* 保存有关所选分割的信息 */
			fc_context->first = false;
			fc_context->ratio = fc_ratio;
			fc_context->overlap = fc_overlap;
			fc_context->right_lower = fc_right_lower;
			fc_context->left_upper = fc_left_upper;
			fc_context->common_left = fc_max_left_count - fc_left_count;
			fc_context->common_right = fc_left_count - fc_min_left_count;
		}
	}
}

/*
 * 查找范围的类编号。
 *
 * 类编号是范围属性的有效组合。注意：最高可能的编号是8，因为 CLS_EMPTY 不能与其他任何东西结合。
 */
static int get_gist_range_class(RangeType *fc_range)
{
	int			fc_classNumber;
	char		fc_flags;

	fc_flags = range_get_flags(fc_range);
	if (fc_flags & RANGE_EMPTY)
	{
		fc_classNumber = CLS_EMPTY;
	}
	else
	{
		fc_classNumber = 0;
		if (fc_flags & RANGE_LB_INF)
			fc_classNumber |= CLS_LOWER_INF;
		if (fc_flags & RANGE_UB_INF)
			fc_classNumber |= CLS_UPPER_INF;
		if (fc_flags & RANGE_CONTAIN_EMPTY)
			fc_classNumber |= CLS_CONTAIN_EMPTY;
	}
	return fc_classNumber;
}

/*
 * range_gist_single_sorting_split 的比较函数。
 */
static int fc_single_bound_cmp(const void *fc_a, const void *fc_b, void *fc_arg)
{
	SingleBoundSortItem *fc_i1 = (SingleBoundSortItem *) fc_a;
	SingleBoundSortItem *fc_i2 = (SingleBoundSortItem *) fc_b;
	TypeCacheEntry *fc_typcache = (TypeCacheEntry *) fc_arg;

	return range_cmp_bounds(fc_typcache, &fc_i1->bound, &fc_i2->bound);
}

/*
 * 按下界比较 NonEmptyRanges。
 */
static int fc_interval_cmp_lower(const void *fc_a, const void *fc_b, void *fc_arg)
{
	NonEmptyRange *fc_i1 = (NonEmptyRange *) fc_a;
	NonEmptyRange *fc_i2 = (NonEmptyRange *) fc_b;
	TypeCacheEntry *fc_typcache = (TypeCacheEntry *) fc_arg;

	return range_cmp_bounds(fc_typcache, &fc_i1->lower, &fc_i2->lower);
}

/*
 * 按上界比较 NonEmptyRanges。
 */
static int fc_interval_cmp_upper(const void *fc_a, const void *fc_b, void *fc_arg)
{
	NonEmptyRange *fc_i1 = (NonEmptyRange *) fc_a;
	NonEmptyRange *fc_i2 = (NonEmptyRange *) fc_b;
	TypeCacheEntry *fc_typcache = (TypeCacheEntry *) fc_arg;

	return range_cmp_bounds(fc_typcache, &fc_i1->upper, &fc_i2->upper);
}

/*
 * 按其增量比较 CommonEntrys。
 */
static int fc_common_entry_cmp(const void *fc_i1, const void *fc_i2)
{
	double		fc_delta1 = ((CommonEntry *) fc_i1)->delta;
	double		fc_delta2 = ((CommonEntry *) fc_i2)->delta;

	if (fc_delta1 < fc_delta2)
		return -1;
	else if (fc_delta1 > fc_delta2)
		return 1;
	else
		return 0;
}

/*
 * 方便函数，调用特定类型的 subtype_diff 函数。
 * 调用者必须已经检查过该范围类型是否存在一个。
 */
static float8 fc_call_subtype_diff(TypeCacheEntry *fc_typcache, Datum fc_val1, Datum fc_val2)
{
	float8		fc_value;

	fc_value = DatumGetFloat8(FunctionCall2Coll(&fc_typcache->rng_subdiff_finfo,
											 fc_typcache->rng_collation,
											 fc_val1, fc_val2));
	/* 通过返回零来应对有缺陷的 subtype_diff 函数 */
	if (fc_value >= 0.0)
		return fc_value;
	return 0.0;
}
